package array.sliding_window;
/*      给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，
        满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

        示例 1：
        输入：nums = [1,2,3,1], k = 3
        输出：true

        示例 2：
        输入：nums = [1,0,1,1], k = 1
        输出：true

        示例 3：
        输入：nums = [1,2,3,1,2,3], k = 2
        输出：false*/
public class lc219 {
    public static void main(String[] args) {
        int[] nums=new int[]{1,0,1,1};
        System.out.println(containsNearbyDuplicate(nums, 1));

    }
    public static boolean  containsNearbyDuplicate(int[] nums, int k) {
        if(nums.length==1) return false;
        if(k==1) {
            for (int i = 0; i < nums.length-1 ; i++) {
                if(nums[i]==nums[i+1]){
                    return true;
                }
            }
        }

          int left=0;
          int right=0;
          int cur_length=0;
          int shortest_length=0;
          while(right< nums.length){
              cur_length=right-left+1;
              while(IsRepeat(nums,left,right)){
                  if(right-left+1<shortest_length||shortest_length==1){
                      shortest_length=right-left+1;
                  }
                  left++;
              }
              right++;
          }
          if(shortest_length==0){return false;}
          return shortest_length-1<=k ? true:false;
        }
        public static boolean IsRepeat(int[] nums,int left,int right){
        if(right-left==0){
            return false;
        }else{
            int[] copy_nums=new int[right-left+1];
            for (int i = 0; i<right-left+1&&i <right+1 ; i++) {
                copy_nums[i]=nums[left+i];
            }
            /*for (int val:copy_nums
                 ) {
                System.out.println(val);
            }*/
            for (int i = 0; i < right-left+1 ; i++) {
                for (int j = 0; j < right-left+1-i-1 ; j++) {
                    if(copy_nums[j+1]<copy_nums[j]){
                        int temp=copy_nums[j];
                        copy_nums[j]=copy_nums[j+1];
                        copy_nums[j+1]=temp;
                    }
                }
            }
            for (int i = 0; i < right-left ; i++) {
                if(copy_nums[i]==copy_nums[i+1]){
                    return true;
                }
            }
            return false;
        }
        }
}
